//package LeetCodeHot100;
//
//public class Q148_SortList {
//    //有点类似合并两个有序链表
//    //本题的要求是在链表上进行归并排序 ==> 一般链表排序的问题往归并上靠
//    //1、我们之前的归并怎么写
//    //2、要求空间复杂度了 必须用迭代写
//    public ListNode sortList(ListNode head) {
//
//        return null;
//    }
//
//    public void process(ListNode head, ListNode tail){
//        //只有一个元素 天然有序
//        if (head == tail){
//            return;
//        }
//        //找中点
//        ListNode midNode = findMidNode(head, tail);
//        //左边有序
//        //在归并排序中 左右节点数量并无要求
//        process(head, midNode);
//        process(midNode.next, tail);
//        merge(head, midNode, tail);
//    }
//
//    public void merge(ListNode head, ListNode mid, ListNode tail){
//
//    }
//
//    //找中点 奇数返回中点 偶数返回上中点
//    public ListNode findMidNode(ListNode head, ListNode tail){
//        //只有一个 或两个 直接返回 head
//        if (head.next == tail){
//            return head;
//        }
//        //三个 支持
//        ListNode fast = head.next.next;
//        ListNode slow = head.next;
//        while (fast.next != null && fast.next.next != null){
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//        return slow;
//    }
//
//
//}
//
//
